package jdk;
/**

 * Perm.java created by zhangzhidong 
 * at 下午7:04:36 2016年10月14日
 */

/**
 * @author zhangzhidong<br>
 * comment generated at 2016年10月14日下午7:04:36<br>
 * 
 */
	import java.util.ArrayList;
	public class Solution {
	    ArrayList<String> res = new ArrayList<String>();
	    public ArrayList<String> Permutation(String str) {
	        if(str==null || str.length()==0) return res;
	        perm(str.toCharArray(),0,str.length()-1);
	         
	        String []strs = new String[res.size()];
	        strs = res.toArray(strs);
	         
	         
	        sort(strs,0,strs.length-1);
	        res.clear();
	        for(String s:strs){
	            res.add(s);
	        }
	        return res;
	    }
	     
	    public void sort(String []strs ,int start,int end){
	        if(start<end){
	            int mid = partation(strs,start,end);
	            sort(strs,start,mid-1);
	            sort(strs,mid+1,end);
	        }
	    }
	     
	    public int partation(String []strs,int begin ,int end){
	             
	            String temp  = strs[begin];
	            while(begin<end){
	                while(begin<end && compare(strs[end],temp)<0){
	                    end--;
	                }
	                while(begin<end && compare(strs[begin],temp)>0){
	                    begin ++;
	                }
	                if(begin<end){
	                    swap(strs,begin,end);
	                }
	            }
	            strs[begin] = temp;
	            return begin;
	         
	     
	    }
	     
	    public void swap(String []strs,int idx1,int idx2){
	        String temp = strs[idx1];
	        strs[idx1] = strs[idx2];
	        strs[idx2] = temp;
	    }
	     
	    public int compare(String str1,String str2){
	     
	        return -str1.compareTo(str2);
	    }
	    public void perm(char[] ch,int start,int end){
	        if (start == end){
	            res.add(new String(ch));
	            return;
	        }
	        for(int i = start;i<=end;i++){
	            if(i==start || ch[start] != ch[i]){
	                swap(ch,start,i);
	                perm(ch,start+1,end);
	                swap(ch,start,i);
	            }
	        }
	    }
	     
	    public void swap(char ch[],int idx1,int idx2){
	        if(idx1==idx2) return;
	        char temp = ch[idx1];
	        ch[idx1] = ch[idx2];
	        ch[idx2] = temp;
	    }
	     
	     



	/**
	 * 下午7:04:36 2016年10月14日
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Solution p = new Solution();
		p.Permutation("abcdef");
		for(int i=0;i<p.res.size();i++){
			if(i==500){
				System.out.println(p.res.get(i));
			}
		}
	
	}

}
